模拟赛题解/2025.8.20 模拟赛

T1-天元超常 2（super）

题面

给出一个 $n$ 个点，$m$ 条边的无向图，每条边有初始颜色 $s_i$ 和目标颜色 $t_i$。

每次操作可以选择一个点将其所有连边转换成任意相同颜色。

需要给出一种操作方案使得图上所有边都变为其目标颜色 $t$，或者报告无解。

$1\leq n,K\leq 2\times10^5,0\leq m\leq 2\times10^5$，其中 $K$ 表示颜色个数。

题解

首先我们注意到，每次操作的处理都要考虑后续带来的变化，而不需要考虑之前的操作。

所以我们倒序地进行操作的分析。

此时问题就被简化成需要找到每一个周围所有 $t_i$ 都相等的点。

于是这就是一个类似于拓扑排序的问题，每次处理的时候使得一部分边不用考虑，再把新产生的符合所有 $t_i$ 都相等的点加入。

最后当没有点可加入时，假如剩余的所有边都是 $s_i=t_i$ 的，就可以输出答案，反之则无解。

用队列维护点，map 或诸如此类的东西维护边的类型，复杂度 $O(n\log n)$

T2-团计数（counting）

题面

对于一个 $n$ 个点，$m$ 条边的简单无向图，求这张图中团的个数对 $10^9+7$ 取模。

对于一张图 $G$，其点集的一个子集 $X$ 被称为一个团当且仅当其导出子图是完全图。

$1\leq n,m\leq 1000$

题解

首先这题是一个 #pc 问题，不存在多项式复杂度的解法，因此我们考虑指数级的算法。

因为边数不超过 $1000$，而一个团内的边数是阶乘级别的，所以显然一个团内的边数不会太多，因此考虑让指数上为 $\sqrt{m}$ 级别。

我们考虑如何缩减每个点的度数，可以使用类似三元环计数的处理方法，将所有点按照编号从小到大排序，只保留编号较小的点到编号较大的点的连边，则新图上每个点的度数是 $\sqrt{2m}$ 级别的，计算答案时枚举每个团中度数最小的点即可。

而 $\sqrt{2m}$ 仍有 $44.7$，显然无法接受，但是可以考虑折半搜索，枚举前后各 $22$ 个点，复杂度就会被控制在合理的范围内。

最后使用 SOSDP 即可，该算法可以在 $O(d2^{\frac{d}{2}})$ 的时间复杂度范围内计算出度数为 $d$ 的点对答案的贡献，因此总复杂度约为 $\sqrt{m}2^{\frac{\sqrt{2m}}{2}}$，常数相当小，可轻松通过。

T3-原野（field）

题面

有一个 $n\times m$ 大小的矩形，其上每个位置都有一个值。

求有多少个子矩形，满足该子矩形内所有值都严格小于与这一位置横坐标或纵坐标相同的边界上的值。

$1\leq n,m\leq 2500,0\leq a_{i,j}\leq 7\times 10^6$

题解

我们注意到因为要求矩形内的数严格小于对应边界上的数，对于 $r_1=r_2$ 的情形，合格的 $(c_1,c_2)$ 构成嵌套集，即不会出现两组 $(c_1,c_2)$ 和 $c_1',c_2'$ 满足它们对应的线段既不是相离关系也不是包含关系，$c_1=c_2$ 同理。

因此，对于每一个 $r_1$，可能成为答案的 $(c_1,c_2)$ 只有 $O(n)$ 组，$c_1$ 同理。求出这些区间可以使用单调栈，这部分是 $O(n^2)$ 的。

考虑一个矩形合法的充要条件，假设 $(r_1,r_1,c_1,c_2)$ 和 $(r_1,r_2,c_1,c_1)$ 合法，我们相当于要让 $\forall i\in[r_1,r_2],(i,i,c_1,c_2)$ 合法（A），以及 $\forall j\in[c_1,c_2],(r_1,r_2,j,j)$ 合法（B）。

我们可以对于每个合法的 $(r_1,r_2,c_1,c_2)$，预处理出 $\text{ed}$ 表示 $r_2\leq\text{ed}$ 时 $\text{A}$ 性质才满足，$\text{B}$ 性质同理，时间复杂度同样为 $O(n^2)$。

枚举矩形的左上角，相当于要求满足条件的 $(r_2,c_2)$ 二元组使得 $r_2\leq \text{ed}_{(r_1,r_1,c_1,c_2)}\land c_2\leq\text{ed}_{(r_1,r_2,c_1,c_1)}$。这是一个二位数点的形式，可以使用树状数组求解，复杂度 $O(n^2\log n)$。

T4-旅途（journey）

题面

在一个 $n$ 个点的数轴上，第 $i$ 个点可以一步到达 $[l_i,r_i]$ 中的点，保证 $i\in[l_i,r_i]$。

可以选择一个点出发，经过一段时间后再次回到这个点，每个点可以走超过一次，设这段路程经过点的点集为 $S$。

求有多少种不同的 $S$ 是可能达到的。

题解

考虑如何 check 一个 $S$ 是否合法。首先题目中的要求等价于 $S$ 对应的导出子图强连通。

结论是，我们每次将 $S$ 中相邻的两个互相可达的 SCC 合并（初始时，每个点自成 一个 SCC），$S$ 合法当且仅当通过上述过程可以将 $S$ 合并为一个 SCC。

证明大概就是考虑假设某次合并了不相邻的两个 SCC，那么一定也可以调整为若干次合并相邻的两个。

但是直接这样做会算重。一种处理方法是，补集转化，$S$ 不合法当且仅当最后留下 了 $>1$ 个 SCC 且相邻无法合并。

记 $f_{i,j,s,t}$ 表示 $S\subset\{i,\cdots,j\}$ ，$\min_{x\in S}l_x=s$， $\max_{x\in S}r_x=t$ 的合法 $S$ 的数量，同时维护一个辅助数组表示若干个相邻之间无法合并 的 SCC 拼起来的方案数即可。时间复杂度视实现在 $O(n^6)\sim O(n^8)$ 之间，由于常数很小理论上均可通过。